package common.sort;

/**
 * 原理:
 * 每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止
 */
public class InsertSort01 implements Sort {

    @Override
    public void sort(int[] array) {
        int LEN = array.length;

        // 1.依次顺序选择元素，拿出来
        // 2.与前一个值对比，tmp < current 向后移动当前元素
        // 3.重复第2步
        // 4.tmp >= current 就插入
        // 5.重复以上步骤
        for (int i = 1; i < LEN; i++) {
            // 保存需要插入的数据
            int tmp = array[i];

            int j = i;
            while (j > 0 && tmp < array[j-1]) {
                array[j] = array[j-1];
                j--;
            }

            if (i != j) {
                array[j] = tmp;
            }
        }
    }
}
